package org.laizili.solution.leetcode;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/cut-off-trees-for-golf-event/">675. 为高尔夫比赛砍树</a>
 * <p>
 * tags: 排序+广度优先搜索;
 */
public class Problem675 {
    private static class Solution {
        // 没有想到 相邻最矮树的最短距离和就是答案
        // 被可以选择砍不砍脚下的树条件迷惑
        private int m, n;

        public int cutOffTree(List<List<Integer>> forest) {
            m = forest.size();
            n = forest.get(0).size();
            List<int[]> trees = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (forest.get(i).get(j) > 1) {
                        trees.add(new int[]{i, j});
                    }
                }
            }
            trees.sort(Comparator.comparingInt(t -> forest.get(t[0]).get(t[1])));
            int x = 0, y = 0;
            int ans = 0;
            for (int[] xy : trees) {
                int steps = bfs(forest, x, y, xy[0], xy[1]);
                if (steps == -1) {
                    return -1;
                }
                ans += steps;
                x = xy[0];
                y = xy[1];
            }
            return ans;
        }

        private static final int[] dirX = new int[]{0, 1, 0, -1};
        private static final int[] dirY = new int[]{1, 0, -1, 0};

        private int bfs(List<List<Integer>> forest, int x, int y, int ex, int ey) {
            if (x == ex && y == ey)
                return 0;
            Queue<int[]> nextXY = new ArrayDeque<>();
            int steps = 0;
            nextXY.offer(new int[]{x, y});
            boolean[][] visited = new boolean[m][n];
            visited[x][y] = true;
            while (!nextXY.isEmpty()) {
                steps++;
                int size = nextXY.size();
                for (int i = 0; i < size; i++) {
                    int[] xy = nextXY.poll();
                    for (int j = 0; j < 4; j++) {
                        int nx = xy[0] + dirX[j];
                        int ny = xy[1] + dirY[j];
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny] && forest.get(nx).get(ny) > 0) {
                            if (nx == ex && ny == ey) {
                                return steps;
                            }
                            visited[nx][ny] = true;
                            nextXY.offer(new int[]{nx, ny});
                        }
                    }
                }
            }
            return -1;
        }

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.cutOffTree(List.of(List.of(1, 2, 3), List.of(0, 0, 4), List.of(7, 6, 5))));
        System.out.println(solution.cutOffTree(List.of(List.of(1, 2, 3), List.of(0, 0, 4), List.of(3, 6, 5))));
        System.out.println(solution.cutOffTree(
                List.of(
                        List.of(54581641, 64080174, 24346381, 69107959),
                        List.of(86374198, 61363882, 68783324, 79706116),
                        List.of(668150, 92178815, 89819108, 94701471),
                        List.of(83920491, 22724204, 46281641, 47531096),
                        List.of(89078499, 18904913, 25462145, 60813308)
                )
        ));
        System.out.println(solution.cutOffTree(List.of(List.of(2, 3, 4), List.of(0, 0, 5), List.of(8, 7, 6))));
    }
}
